//四数之和 力扣18
//两层for循环+双指针 剪枝 去重 去重顺序 边界判断 
class Solution {
public:
	vector<vector<int>> fourSum(vector<int>& a, int target) {
		sort(a.begin(),a.end());
		int len = a.size();
		vector<vector<int>> ans;
		if(len < 3) return ans;
		
		for(int i = 0; i < len-3; i++)
		{
			//剪枝
			if(a[i] > target && a[i] >= 0) return ans;
			//去重
			if(i > 0 && a[i] == a[i-1]) continue;
			for(int j = i+1; j < len - 2; j++)
			{
				//剪枝
				if(a[i]+a[j] > target && a[i]+a[j] >= 0) break;
				//去重
				if(j > i + 1 && a[j] == a[j-1]) continue;
				
				int l = j+1;
				int r = len-1;
				while(l < r)
				{
					if((long)a[i]+a[j]+a[l]+a[r] > target) r--;
					else if((long)a[i]+a[j]+a[l]+a[r] < target) l++;
					else
					{
						ans.push_back({a[i],a[j],a[l],a[r]});
						while(l<r && a[l]==a[l+1]) l++;
						while(l<r && a[r]==a[r-1]) r--;
						r--;
						l++;
					}
				}
				
			}
		}
		return ans;
	}
};
